import bean.TreeNode;


public class Leetcode1372 {
    public static void main(String[] args) {

    }

    int max = 0;

    /**
     * 根节点是右节点
     * @param root
     * @return
     */
    public int longestZigZag(TreeNode root) {
        if (root == null){
            return 0;
        }
        max = Math.max(max, dfs(root.right, false,  1));
        max = Math.max(max, dfs(root.left, true,  1));
        return max;
    }

    /**
     * 如果自己是右节点，则判断是否有左节点,没有左节点，则返回最大值，有左节点，则继续向下遍历
     * 如果自己是左节点，则判断是否有右节点，有右节点，则返回值作为最大值，没有，则继续向下遍历
     * @param node
     * @param isLeft
     * @return
     */
    public int dfs(TreeNode node, boolean isLeft, int num){
        if (node == null){
            return num;
        }

        // 如果当前node是左节点
        if (isLeft){

            if (node.right != null){
                // 判断是否有右节点，有右节点，则继续深度遍历下去，num = num +1
                max = Math.max(max, dfs(node.right, false, num + 1));

            }else{
                // 没有又节点，则右节点为空，遍历结束，返回num
                max = Math.max(max, num);
            }

            // 左节点重新开始遍历
            max = Math.max(max, dfs(node.left, true, 0));
        }else {
            if (node.left != null){
                max = Math.max(max, dfs(node.left, true, num + 1));
            }else{
                max = Math.max(max, num);
            }

            max = Math.max(max, dfs(node.right, false, 0));
        }
        return max;
    }


}
